package com.origin.niuke.simulation;

import java.util.ArrayList;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/4/29 10:13
 * 螺旋矩阵
 * 给定一个m x n大小的矩阵（m行，n列），按螺旋的顺序返回矩阵中的所有元素。
 * 算法：数组 + 模拟
 */
public class NC38 {
    public static void main(String[] args) {
        System.out.println(new NC38().spiralOrder(new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}));
    }

    public ArrayList<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> ans = new ArrayList<>();
        int n = matrix.length;
        if (n == 0) return ans;
        int m = matrix[0].length;
        int left = 0, right = m - 1, up = 0, bottom = n - 1;
        while (left <= right && up <= bottom) {
            for (int i = left; i <= right; i++) ans.add(matrix[up][i]);
            for (int i = up + 1; i <= bottom; i++) ans.add(matrix[i][right]);
            // 判断，当只剩一个数的时候，会重复遍历，所以要做判断
            if (left < right && up < bottom) {
                for (int i = right - 1; i >= left; i--) ans.add(matrix[bottom][i]);
                for (int i = bottom - 1; i >= up + 1; i--) ans.add(matrix[i][left]);
            }
            ++left; --right; ++up; --bottom;
        }
        return ans;
    }

    /*
    以上方法是螺旋矩阵通用的, 本题中给出了矩阵中的元素的绝对值 ≤ 100
    因此可以使用这个条件作为向右转的依据
    方向数组要顺时针, 右 -> 下 -> 左 -> 上
     */
    int[][] direction = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    public ArrayList<Integer> spiralOrder2(int[][] matrix) {
        ArrayList<Integer> ans = new ArrayList<>();
        int n = matrix.length;
        if (n == 0) return ans;
        int m = matrix[0].length;
        for (int i = 0, j = 0, d = 0; ans.size() != n * m;) {
            ans.add(matrix[i][j]);
            matrix[i][j] = 101;
            int newI = i + direction[d][0], newJ = j + direction[d][1];
            if (newI < 0 || newI >= n || newJ < 0 || newJ >= m || matrix[newI][newJ] == 101) {
                d = (d + 1) % 4;
                i += direction[d][0]; j += direction[d][1];
            } else {
                i = newI;
                j = newJ;
            }
        }
        return ans;
    }

}
